# -*- coding:utf-8 -*-
def find_max(arr):
    if arr is None or len(arr) == 0:
        return 0

    max_sum = cur_sum = float('-inf')
    for num in arr:
        if cur_sum <= 0:
            cur_sum = num
        else:
            cur_sum += num
        if cur_sum > max_sum:
            max_sum = cur_sum

    return max_sum


"""
对每一行，与下面行累加，得到一个一维数组，用一维数组求连续子数组的最大和的方式求出最大和。O(N^2)
"""


def find_max_matrix(matrix, n):
    if n <= 0:
        return 0
    max_sum = float('-inf')
    row = len(matrix)  # 行数
    for i in range(row):
        sum_arr = matrix[i]
        cur_sum = find_max(sum_arr)
        if cur_sum > max_sum:
            max_sum = cur_sum
        for j in range(i + 1, row):
            sum_arr = [sum_arr[x] + matrix[j][x] for x in range(len(sum_arr))]
            cur_sum = find_max(sum_arr)
            if cur_sum > max_sum:
                max_sum = cur_sum
    return max_sum


class SubMatrix:
    def sumOfSubMatrix(self, mat, n):
        return find_max_matrix(mat, n)


if __name__ == "__main__":
    print(find_max_matrix([[1, 2, -3], [3, 4, -5], [-5, -6, -7]], 3))
